Problem statement: zenit15skg

Na pomarančovej plantáži sa vypestovali, prekvapivo, pomaranče. Plantáž dostáva ponuky na odber kusov v rôznych hmotnostných kategóriach. Problém je že kupcovia vyžadujú exkluzívny odber. Na výber správnej zmluvy treba spočítať čo sa oplatí. Počet pomarančov je najdôležitejší ukazateľ. Z inventárneho zoznamu pomarančov a ponúk zistite množstvá prípadne predaných pomarančov.

Formát vstupu a výstupu

Prvý riadok vstupu obsahuje počet pomarančov \(N\). Toto číslo nepresiahne \(100000\). Na druhom riadku je \(N\) kladných celých veľkostí pomarančov. Pomaranče môžu mať najviac \(1000000\) gramov a sú na vstupe utriedené od najmenšieho po najväčší. Tretí riadok má počet ponúk \(M\), najviac \(10000\). Nasleduje \(M\) riadkov z dvoma číslami \(a\) \(b\) vyjadrujúce že daná ponuka je na veľkosti pomarančov od \(a\) po \(b\) vrátane. Pre každú ponuku vypíšte v poradí počet pomarančov ktorých sa týka.

Príklady

Input:

8
1 2 3 4 5 6 7 8
3
1 5
2 4
3 6

Output:

5
3
4